//package work.rightAnswer;
//
//import java.util.LinkedList;
//import java.util.Queue;
//
////深度优先遍历：比较直观，每次都能遍历到最底层。不必创建数结构或节点储存遍历参数，可以借用JVM函数栈帧存储。有死循环的风险
////层序遍历：不够直观，需要创建一个数据结构或节点储存层序遍历变量
//class Solution_bfs_909 {
//    public int snakesAndLadders(int[][] board) {
//        int n = board.length;
//        //由于遍历方式是逐次递增的层序遍历，所以：
//        //1.访问同一个节点位置，先访问时的移动次数肯定更小，这也就省去了我们比较的步骤（二维数组，储存value和移动次数），直接用一个bool储存一个是否访问数组即可
//        //2.先爬梯子，肯定比后爬梯子要更快
//        boolean[] visited = new boolean[n*n+1];
//        //队列存放 {1,0} 值为1，移动次数为0
//        Queue<int[]> queue = new LinkedList<>();
//        queue.offer(new int[]{1,0});
//        //层序遍历
//        while (!queue.isEmpty()){
//            //出队，遍历
//            int[] poll = queue.poll();
//            int value = poll[0];
//            for (int i = value+1; i <= Math.min(value+6,n*n); i++) {
//                int num = i;
//                //入队
//                int[] site = getSite(num, n);
//                //有梯子
//                if(board[site[0]][site[1]]>0){
//                    num = board[site[0]][site[1]];
//                }
//                //到达终点
//                if(num==n*n){
//                    return poll[1]+1;
//                }
//                if(!visited[num]){
//                    visited[num] = true;
//                    queue.offer(new int[]{num,poll[1]+1});//扩展新状态
//                }
//
//            }
//
//        }
//
//        return -1;
//    }
//
//
//    //通过当前value值，获取坐标
//    public int[] getSite(int value,int n){
//        //如果大于n平方，返回-1，等于n平方，返回level
//        // 36 n*n-1+n [0,0] 35 n*n-1+n-1 [0,1] ... n*n-1+1 [0,n-1]
//        // 25 n*n-2+1 [1,0] 26 n*n-2+2 [1,1] ...30 n*n-2+n [1,n-1]
//        //根据上面，不难得规律。 (n-i-1)%2==1 奇数列 符合 当前数为(n-i-1)*n+j+1 (n-i-1)%2==0 偶数列 符合 当前数为(n-i-1)*n+j+1
//        //相反可推： 如果为奇数列，符合value =(n-i-1)*n+j+1 ;偶数列，则符合value=(n-i-1)*n+j+1
//        // (n-1-i) = (value-1)/n; i=(n-1)-(value-1)/n;
//        // if((n-i)%2==1) j=(value-1)%n+1  else n-1-j=(value-1)%n 即 j=(n-1)-(value-1)%n
//        int i = (n-1)-(value-1)/n;
//        int j;
//        if((n-i)%2==1){
//            j=(value-1)%n;
//        }else {
//            j=(n-1)-(value-1)%n;
//        }
//
//        return new int[]{i,j};
//    }
//}